package top.humbleyuan.tree;

import top.humbleyuan.datastructure.tree.TreeNode;
import util.MyListHandle;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/19 19:22
 * @Des 二叉树的中序遍历
 */
public class LeetCode_94 {
    public static void main(String[] args) {
        // 递归
        m1();

        // 循环
        m2();
    }

    // 递归
    public static void m1() {
        TreeNode head1 = new TreeNode(2);
        head1.formTree();

        List<Integer> traverse = new ArrayList<>();

        //递归
        recursion(head1,traverse);

        System.out.println("递归" + MyListHandle.ListToString(traverse));
    }

    //中序递归
    public static void recursion(TreeNode head,List<Integer> traverse) {
        if(head != null) {
            if(head.left != null)
                recursion(head.left,traverse);
            traverse.add(head.val);

            if(head.right != null)
                recursion(head.right,traverse);
        }
    }

    // 循环迭代
    public static void m2() {
        TreeNode head1 = new TreeNode(2);
        head1.formTree();

        List<Integer> traverse2 = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode temp = head1;
        while (!stack.empty() || temp != null) {

            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }

            //左树为空
            temp = stack.pop();
            traverse2.add(temp.val);

            //然后到最底层的右树
            temp = temp.right;

        }

        System.out.println("递归" + MyListHandle.ListToString(traverse2));
    }
}
